package com.leetcode;

import org.testng.annotations.Test;

public class ValidPalindrome {
	public boolean isPalindrome(String s) {
		char[] ch = s.replaceAll("[^\\w\\d]", "").toLowerCase().toCharArray();
		int N = ch.length;
		for (int i=0; i<(N+1)/2; i++) {
			if (ch[i] != ch[N-1-i]) return false;
		}
		return true;
	}
	
	public boolean isPalindrome2(String s) {
		char[] ch = s.toLowerCase().toCharArray();
		int i = 0;
		int j = ch.length-1;
		
		while (i < j) {
			if (!isAlphaNumeric(ch[i])) {
				i++;
			} else if (!isAlphaNumeric(ch[j])) {
				j--;
			} else if (ch[i++] != ch[j--]) {
				return false;
			}
		}
		
		return true;
	}
	
	private boolean isAlphaNumeric(char c) {
		return (c>='a' && c<='z') || (c>='0' && c<='9');
	}
	
	@Test
	public void test1() {
		new ValidPalindrome().isPalindrome2("a ba");
	}
}
